package algorithm.easy;

import pojo.TreeNode;

/**
 * 列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。请你对 arr 应用下述算法：
 * <p>
 * 从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾。
 * 重复上面的步骤，但这次是从右到左。也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。
 * 不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。
 * 给你整数 n ，返回 arr 最后剩下的数字。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 9
 * 输出：6
 * 解释：
 * arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
 * arr = [2, 4, 6, 8]
 * arr = [2, 6]
 * arr = [6]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/elimination-game
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LastRemaining390 {

    /**
     * a0->a0+d or a0
     * d->2d
     * num->num/2
     * left_to_right = true or false
     * <p>
     * 从左向右删除，总共有奇数个数字（第一位要删掉，最后一位要删掉）
     * 从左向右删除，总共有偶数个数字（第一位要删掉，最后一位不用删掉）
     * 从右向左删除，总共有奇数个数字（第一位要删掉，最后一位要删掉）
     * 从右向左删除，总共有偶数个数字（第一位不用删掉，最后一位要删掉）
     */
    public int lastRemaining(int n) {
        int a = 1;
        int d = 1;
        boolean left_to_right = true;
        while (n > 1) {
            if (n % 2 == 1) {
                //奇数个数字 a0 = a0 + d;
                a = a + d;
            } else {
                //偶数个数字
                if (left_to_right) {
                    //从左到右
                    a = a + d;
                }
            }
            d = 2 * d;
            n = n / 2;
            left_to_right = !left_to_right;
        }
        return a;
    }

}
